/**
 * @author zhangmin
 * @create 2022-07-31 20:22
 * 字节提前批一面--螺旋顺时针打印矩阵
 * 从（x，y）开始，顺时针打印矩阵
 * 例子：
 * 12 13 14 15
 * 11 2  3  4
 * 10 1  0  5
 * 9  8  7  6
 * x=2,y=2,则答案为：0->1->2->3...15
 * x=2,y=1,则答案为：1->10->11->2->3->0->7->8->9
 */
public class PrintMatrix0729 {
    static int[][] direct=new int[][]{{0,-1},{-1,0},{0,+1},{+1,0}};
    static boolean[][] visited;
    //needToGo记录在dir这个方向上一共需要走几步，每换一次左右方向就要加1，hadGo表示在当前方向已经走了几步了
    public static void backtrack(int[][] matrix,int row,int col,int dir,int needToGo,int hadGo){
        int m=matrix.length,n=matrix[0].length;
        if (row<0||row>=m||col<0||col>=n||visited[row][col]) return;
        visited[row][col]=true;
        System.out.print(matrix[row][col]);
        System.out.print(" ");
        if (hadGo==needToGo){
            //需要换方向了
            if (dir%2==1){
                //当前是向上或者向下，则needTo+1
                dir=(dir+1)%4;
                backtrack(matrix,row+direct[dir][0],col+direct[dir][1],dir,needToGo+1,1);
            }else {
                dir=(dir+1)%4;
                backtrack(matrix,row+direct[dir][0],col+direct[dir][1],dir,needToGo,1);
            }
        }else {
            backtrack(matrix,row+direct[dir][0],col+direct[dir][1],dir,needToGo,hadGo+1);
        }
    }
    public static void main(String[] args) {
        int[][] matrix=new int[][]{{12,13,14,15},{11,2,3,4},{10,1,0,5},{9,8,7,6}};
        int x=3,y=3;
        int m=matrix.length,n=matrix[0].length;
        visited=new boolean[m][n];
        backtrack(matrix,x,y,0,1,0);
    }
}
